'''
Treap 动态空间实现
'''
import random

class Node:

    def __init__(self, key, value, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
        self.priority = random.random()
    def __repr__(self):
        return f'key: {self.key}, value: {self.value}, priority: {self.priority:.5f}'


class TreapTree:
    def __init__(self):
        self.root = None
        self.size = 0

    def _left_rotate(self, node):  # 左旋,左边节点为新头，同时保证仍为搜索树
        right = node.right  # 不判空，因为只有不平衡才调用，所以默认右肯定有
        node.right = right.left
        right.left = node
        return right

    def _right_rotate(self, node):  # 与左旋对称相似
        left = node.left
        node.left = left.right
        left.right = node
        return left

    def _maintain(self, node):
        if not node: return None
        if node.left and node.left.priority > node.priority:
            node = self._right_rotate(node)
        if node.right and node.right.priority > node.priority:
            node = self._left_rotate(node)
        return node


    def _get(self, node, k):
        if node is None:
            return None
        elif k < node.key:
            return self._get(node.left, k)
        elif k > node.key:
            return self._get(node.right, k)
        return node

    def _add(self, node, k, v):
        if node is None:
            self.size += 1
            return Node(k, v)
        elif k < node.key:
            node.left = self._add(node.left, k, v)
        elif k > node.key:
            node.right = self._add(node.right, k, v)
        else:
            node.value = v
        return self._maintain(node)

    def _delete(self, node, k):
        if k < node.key:
            node.left = self._delete(node.left, k)
        elif k > node.key:
            node.right = self._delete(node.right, k)
        else:
            # 没左没右直接删，只有一个孩子节点，孩子节点替换我
            if not node.left:
                node = node.right
            elif not node.right:
                node = node.left
            else:
                # 既有左又有右利用堆的特性，来维护
                if node.left.priority >= node.right.priority:
                    node = self._right_rotate(node)
                    node.right = self._delete(node.right, k)
                else:
                    node = self._left_rotate(node)
                    node.left = self._delete(node.left, k)
        return self._maintain(node)

    # ******************** 基本api ****************************
    def put(self, key, value):
        self.root = self._add(self.root, key, value)

    def get(self, key):
        target = self._get(self.root, key)
        if not target: raise KeyError(key)
        return target.value

    def remove(self, key):
        if self._get(self.root, key):
            self.size -= 1
            self.root = self._delete(self.root, key)
            pass

    def get_size(self):
        return self.size

    __getitem__ = get
    __setitem__ = put
    __delitem__ = remove
    __len__ = get_size

    def floor(self, key):
        def f(root):
            if root is None: return float('-inf')
            if key < root.key:
                return f(root.left)
            elif key > root.key:
                return max(root.key, f(root.right))
            else:
                return root.key

        return f(self.root)

    def ceil(self, key):
        def f(root):
            if root is None: return float('inf')
            if key < root.key:
                return min(root.key, f(root.left))
            elif key > root.key:
                return f(root.right)
            else:
                return root.key

        return f(self.root)

    def is_bst(self):
        def f(root):
            if not root: return True, float('inf'), float('-inf')
            linfo = f(root.left)
            rinfo = f(root.right)
            is_bst = linfo[0] and rinfo[0] and linfo[2] < root.key < rinfo[1]
            minv = min(linfo[1], root.key, rinfo[1])
            maxv = max(linfo[2], root.key, rinfo[2])
            return is_bst, minv, maxv
        return f(self.root)[0]
